#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define BLOCK_SIZE 4
#define COUNT 2000
int size = 0;
void showScore(int* arr);
//顺序查找算法
int SequentialSearch(int* arr,int sz,int k)
{
    
    assert(arr);
    for(int i = 0;i < sz;i++)
    {
        if(*(arr + i) == k)
        {
            return i;
        }
    }
    return -1;
}
//二分查找
int BinarySearch(int* arr,int sz,int k)
{
    assert(arr);
    int left = 0;
    int right = sz - 1;
    while(left <= right)
    {
        int mid = left + (right - left) /2;
        if(*(arr + mid) < k) left = mid + 1;
        else if(*(arr + mid) > k) right = mid - 1;
        else if(*(arr + mid) == k) return mid;
    }
    return -1;
}
// 比较函数
int compare(const void *a, const void *b)
{
    return (*(int*)a - *(int*)b);
}
//分块查找
int BlockSearch(int* arr, int sz, int k) 
{
    assert(arr);
    int blockSize = BLOCK_SIZE;
    int numBlocks = (sz + blockSize - 1) / blockSize;
    int *index = (int*)malloc(numBlocks * sizeof(int));
    
    for (int i = 0; i < numBlocks; i++)
    {
        int blockStart = i * blockSize;
        int blockEnd = (i + 1) * blockSize - 1;
        if (blockEnd >= sz) blockEnd = sz - 1;
        *(index + i) = *(arr + blockEnd);
    }
    int left = 0, right = numBlocks - 1;
    int blockIndex = -1;
    while (left <= right)
    {
        int mid = left + (right - left) / 2;
        if (k <= index[mid])
        {
            blockIndex = mid;
            right = mid - 1;
        }
        else left = mid + 1;
    }
    if (blockIndex != -1)
    {
        int blockStart = blockIndex * blockSize;
        int blockEnd = (blockIndex + 1) * blockSize - 1;
        if (blockEnd >= sz)
        {
            blockEnd = sz - 1;
        }
        for (int i = blockStart; i <= blockEnd; i++)
        {
            if (arr[i] == k)
            {
                free(index);
                return i;
            }
        }
    }

    free(index);
    return -1;
}
//交换函数
void Swap(int* x,int* y)
{
    int z = *x;
    *x = *y;
    *y = z;
}
//快排hoare版本找基准值
int _QuickSort(int* arr,int left,int right)
{
    int keyi= left;
    left++;
    while(left <= right)
    {
        while(left <= right && *(arr + right) > *(arr + keyi)) right--;
        while(left <= right && *(arr + left) < *(arr + keyi)) left++;
        if(left <= right) Swap(arr + right--,arr + left++);
    }
    Swap(arr + right,arr + keyi);
    return right;
}
//快排
void _QuickSort_(int* arr,int left,int right)
{
    if(left >= right) return;
    int keyi = _QuickSort(arr,left,right);
    _QuickSort_(arr,left,keyi - 1);
    _QuickSort_(arr,keyi + 1,right);
}
//封装快排
void QuickSort(int* arr,int sz)
{
    _QuickSort_(arr,0,sz - 1);
}
//顺序查找
void Sequential(int* arr)
{

    showScore(arr);
    int score = 0;
    printf("请输入要查找的成绩:>");
    scanf("%d",&score);
    //调用函数指针数组
    int find = SequentialSearch(arr,size,score);
    if(find != -1)
    {
        printf("该成绩找到了,在第%d个位置\n",find+1);
    }
    else printf("该成绩没有找到!!!\n");
}
//二分查找
void Binary(int* arr)
{
    int* scoreArr = (int*)malloc(sizeof(int)*size);
    if(scoreArr == NULL)
    {
        perror("malloc error!!!\n");
        exit(1);
    }
    for(int i = 0;i < size;i++)
    {
        *(scoreArr + i) = *(arr + i);
    }
    QuickSort(scoreArr,size);
    int score = 0;
    printf("请输入要查询的成绩:>");
    scanf("%d",&score);
    int find = BinarySearch(scoreArr,size,score);
    if(find != -1)
    {
        printf("该成绩存在!!!\n");
    }
    else printf("该成绩没有找到!!!\n");
    free(scoreArr);
}
//分块查找
void Block(int* arr)
{
    int* scoreArr = (int*)malloc(sizeof(int)*size);
    if(scoreArr == NULL)
    {
        perror("malloc error!!!\n");
        exit(1);
    }
    for(int i = 0;i < size;i++)
    {
        *(scoreArr + i) = *(arr + i);
    }
    QuickSort(scoreArr,size);
    int score = 0;
    printf("请输入要查询的成绩:>");
    scanf("%d",&score);
    int find = BlockSearch(scoreArr,size,score);
    if(find != -1)
    {
        printf("该成绩存在!!!\n");
    }
    else printf("该成绩没有找到!!!\n");
    free(scoreArr);
}
//学生成绩管理系统显示界面
void show()
{
    printf("-------------------------------------\n");
    printf("           学生成绩管理系统            \n");
    printf("-------------------------------------\n");
    printf("             0.退出                  \n");
    printf("             1.添加成绩               \n");
    printf("             2.删除成绩               \n");
    printf("             3.修改成绩               \n");  
    printf("             4.成绩排序               \n");
    printf("             5.菜单显示               \n");
    printf("             6.显示成绩               \n");
    printf("             7.顺序查找               \n");
    printf("             8.折半查找               \n");
    printf("             9.分块查找               \n");
    printf("-------------------------------------\n");
}
//添加成绩
void AddScore(int* arr)
{
    int count = 0;
    int score = 0;
    char c = '\0';
    
    printf("请输入要插入的成绩的个数:>");
    scanf("%d",&count);
    printf("请输入%d个成绩:>",count);
    int index = 0;
    for(int i = count;i > 0;i--)
    {
        scanf("%d",&score);
        *(arr + index++) = score;
    }
    size += count;
    printf("成绩添加完成!!!\n");
}
//删除成绩
void DelScore(int* arr)
{
begin:
    printf("删除成绩的范围只能是1~%d,否则会越界!!!\n",size);
    showScore(arr);
    int del = 0;
    printf("请输入要删除第几个成绩:>");
    scanf("%d",&del);
    if(del >= 1 && del <= size)
    {
        for(int i = del - 1;i < size;i++)
        {
            *(arr + i) = *(arr + i + 1);
        }
        size -= 1;
    }
    else
    {
        printf("越界了,请重新输入!!!\n");
        goto begin;
    }
    printf("删除完成!!!\n");
}
//修改成绩
void ModifyScore(int* arr)
{
    begin:
    printf("修改成绩的范围只能是1~%d,否则会越界!!!\n",size);
    showScore(arr);
    int modify = 0;
    printf("请输入要修改第几个成绩:>");
    scanf("%d",&modify);
    if(modify >= 1 && modify <= size)
    {
        printf("请输入第%d个成绩修改之后的成绩:>",size);
        int value = 0;
        scanf("%d",&value);
        *(arr + modify - 1) = value;
    }
    else
    {
        printf("越界了,请重新输入!!!\n");
        goto begin;
    }
    printf("修改完成!!!\n");
}
//学生成绩界面显示
void showScore(int* arr)
{
    printf("|---------------------------------------|\n");
    printf("                   成绩                  \n");
    printf("|---------------------------------------|\n");
    for(int i = 0;i < size;i++)
    {
        if(i % 10 == 0 && i != 0)
        {
            printf("\n");
            printf("-----------------------------------------\n");
        } 
        printf("|%3d",*(arr + i));
    }
    printf("\n");
}
void FindAlgorithm()
{
    show();
    int input = 0;
    int* arr = (int*)malloc(sizeof(int)*COUNT);
    if(arr == NULL)
    {
        perror("malloc error\n");
        exit(1);
    }
    do
    {
        printf("请输入序号:>");
        scanf("%d",&input);
        switch(input)
        {
            case 0:
                printf("已经退出学生管理系统!!!\n");
            break;
            case 1:
                AddScore(arr);
            break;
            case 2:
                DelScore(arr);
            break;
            case 3:
                ModifyScore(arr);
            break;
            case 4:
                QuickSort(arr,size);
            break;
            case 5:
                show();
                printf("成绩排序完成!!!\n");
            break;
            case 6:
                showScore(arr);
            break;
            case 7:
                Sequential(arr);
            break;
            case 8:
                Binary(arr);
            break;
            case 9:
                showScore(arr);
            break;
            default:
                printf("输入错误!!!\n");
            break;
        }
    }
    while(input);
    free(arr);
}
int main()
{
    FindAlgorithm();
    return 0;
}